/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/merge-intervals
   @Language: C++
   @Datetime: 16-02-09 04:51
   */

/**
 * Definition of Interval:
 * struct Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * };
 */

class Solution {
	static bool intervaless(const Interval &i, const Interval &j){
		return i.start < j.start;
	}

public:
	/**
	 * @param intervals: interval list.
	 * @return: A new interval list.
	 */
	vector<Interval> merge(vector<Interval> &A) {
		// write your code here
		if (A.size()<2) return A;
		sort(A.begin(), A.end(),intervaless);
		vector<Interval> ans(1,A[0]);
		for(int i=1; i<A.size(); ++i){
			if (ans.back().end<A[i].start) ans.push_back(A[i]);
			else ans.back().end=max(ans.back().end,A[i].end);
		}
		return ans;
	}
};
